package com.wj.sort;

/**
 * 快速排序
 * @author wen.jie
 * @date 2021/8/6 9:15
 */
public class Quick extends AbstractSort{

    public static void sort(Comparable[] a){
        sort(a, 0, a.length-1);
    }

    public static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        //分组,返回是分组的分界值所在的索引
        int partition = partition(a, lo, hi);
        //左子组有序
        sort(a, lo, partition - 1);
        //右子组有序
        sort(a, partition+1, hi);
    }

    /**
     * 对数组a中,从索引lo到索引hi之间的元素进行分组,并返回分组界限对应的索引
     * 分界值是变换后的索引
     * @author wen.jie
     * @date 2021/8/6 9:21
     */
    public static int partition(Comparable[] a, int lo, int hi){
        Comparable key = a[lo];
        int left = lo;
        int right = hi+1;
        while (true){

            while (less(key, a[--right])){
                //找到的元素比分界值大
                if (right == lo){
                    break;
                }
            }
            while (less(a[++left], key)){
                //找到的元素比分界值小
                if (left == hi){
                    break;
                }
            }
            if(left >= right) break;
            else exchange(a, left, right);
        }
        exchange(a, lo, right);
        return right;
    }

}
